(** 
    Depth.ml    
    Compute the Depth-first search until a depth of N. See depth.mli 
    for more details about the functions.

    Bozman Çagdas <bozman.cagdas@gmail.com> - 2011
    Razakamiadana Tefin <tefy.razaka@gmail.com>   - 2011
*)

open Utils
open Sets

let dfs title depth stop =  
  let visited_link : StringSet.t ref = ref StringSet.empty  in  
  let is_in link = StringSet.mem link !visited_link in  
  let add_link link = visited_link := StringSet.add link !visited_link in
  if !stop || depth = 0 || Str.string_match ignore title 0 then
    StringSet.empty
  else
    let empty, union = StringSet.empty, StringSet.union in
    debug "Getting links from [P %s <= %d] [current depth : 1] [%s] ... \n" 
      title depth title; flush stderr;
    let page = Page.init title in
    (* Getting all backlinks to distance 1 *)
    let set0 = Page.backlinks_titles page in
    (* Getting all inlinks to distance 1 *)
    let set0 = union set0 (Page.inlinks_titles page) in    
    (* Getting 'depth - 1' times backlinks and inlinks *)
    let rec aux set accu cpt = 
      if depth = cpt then accu
      else
	let new_set = 
	  StringSet.fold
	    (fun w accu_set -> 
	      if !stop || (is_in w) || Str.string_match ignore w 0 
	      then accu_set
	      else
		begin
		  add_link w;
		  debug "Getting links from [P %s <= %d] [current depth : %d] [%s] ... \n" 
		    title depth (cpt + 1) w; flush stderr;
		  let w_page = Page.init w in
		  let sback = Page.backlinks_titles w_page in
		  debug "   ... backlinks\n"; flush stderr;
		  let sin = Page.inlinks_titles w_page in
		  debug "   ... inlinks\n"; flush stderr;
		  union (union accu_set sback) sin
		end)
	    set
	    StringSet.empty
	in
	aux new_set (new_set :: accu) (cpt + 1)
    in
    let all_sets = aux set0 [ set0 ] 1  in
    List.fold_left union empty all_sets     
